#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        int m = nums.size();
        int left = 0, right = m-1;
        if(m == 0)
            return {-1, -1};
        int begin = -1, end = -1;
        while(left < right)
        {
            int mid = left + (right-left)/2;
            if(nums[mid] < target)
            {
                left = mid+1;
            }
            else
            {
                right = mid;
            }
        }
        if(nums[left] != target)
            return {-1, -1};
        else
            begin = left;

        left = 0;right = m-1;
        while(left < right)
        {
            int mid = left+(right-left+1)/2;
            if(nums[mid] > target)
            {
                right = mid-1;
            }
            else
            {
                left = mid;
            }
        }
        if(nums[right] == target)
            end = right;
        return {begin, end};
    }
};
